//你有 4 张写有 1 到 9 数字的牌。你需要判断是否能通过 *，/，+，-，(，) 的运算得到 24。 
//
// 示例 1: 
//
// 输入: [4, 1, 8, 7]
//输出: True
//解释: (8-4) * (7-1) = 24
// 
//
// 示例 2: 
//
// 输入: [1, 2, 1, 2]
//输出: False
// 
//
// 注意: 
//
// 
// 除法运算符 / 表示实数除法，而不是整数除法。例如 4 / (1 - 2/3) = 12 。 
// 每个运算符对两个数进行运算。特别是我们不能用 - 作为一元运算符。例如，[1, 1, 1, 1] 作为输入时，表达式 -1 - 1 - 1 - 1 是不允
//许的。 
// 你不能将数字连接在一起。例如，输入为 [1, 2, 1, 2] 时，不能写成 12 + 12 。 
// 
// Related Topics 数组 数学 回溯 
// 👍 330 👎 0

  
package com.zwy.leetcode.editor.cn;

import java.util.LinkedList;

/**
 * @author zwy 
 */
public class Two4Game {
    public static void main(String[] args) {
        Solution solution = new Two4Game().new Solution();
        int[] arr = {3,4,6,7};
        boolean flag = solution.judgePoint24(arr);
        System.out.println(flag);
    }

    /**
     * 时间复杂度为:
     *
     * @author zwy
     */
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        private double[] arr = new double[3];
        private double[] arr0 = new double[2];
        private boolean flag = false;

        public boolean judgePoint24(int[] cards) {
            back4(new LinkedList<Integer>(), cards, 0);
            return flag;
        }

        private void back4(LinkedList<Integer> list, int[] cards, int start) {
            int count = 0;
            if (list.size() == 2) {
                for (int i = 0; i < 4; i++) {
                    if (!list.contains(i)) {
                        arr[count] = cards[i];
                        count++;
                    }
                }

                for (int i = 0; i < 5; i++) {
                    if (i == 0) {
                        arr[2] = cards[list.get(0)] + cards[list.get(1)];
                    } else if (i == 1) {
                        arr[2] = Math.abs(cards[list.get(0)] - cards[list.get(1)]);
                    } else if (i == 2) {
                        arr[2] = (double) cards[list.get(0)] * (double) cards[list.get(1)];
                    } else if (i == 3) {
                        arr[2] = (double) cards[list.get(0)] / (double) cards[list.get(1)];
                    } else if (i == 4) {

                        arr[2] = (double)cards[list.get(1)] / (double)cards[list.get(0)];
                    }

                    back3(new LinkedList<Integer>(), arr, 0);
                }
                return;
            }
            for (int i = start; i < 4; i++) {
                if (list.contains(i)) {
                    continue;
                }
                list.add(i);
                back4(list, cards, i + 1);
                list.removeLast();
            }
        }

        public void back3(LinkedList<Integer> list, double[] arr, int start) {
            int count = 0;
            if (list.size() == 2) {
                for (int i = 0; i < 3; i++) {
                    if (!list.contains(i)) {
                        arr0[count] = arr[i];
                        count++;
                    }
                }
                for (int i = 0; i < 5; i++) {
                    if (i == 0) {
                        arr0[1] = arr[list.get(0)] +  arr[list.get(1)];
                    } else if (i == 1) {
                        arr0[1] = Math.abs( arr[list.get(0)] -  arr[list.get(1)]);
                    } else if (i == 2) {
                        arr0[1] =  arr[list.get(0)] *  arr[list.get(1)];
                    } else if (i == 3) {
                        if (arr[list.get(1)] == 0) {
                            continue;
                        }
                        arr0[1] = arr[list.get(0)] / arr[list.get(1)];
                    } else if (i == 4) {
                        if (arr[list.get(0)] == 0) {
                            continue;
                        }
                        arr0[1] = arr[list.get(1)] / arr[list.get(0)];
                    }
                    if (arr0[0] + arr0[1] == 24.0 || arr0[0] - arr0[1] == 24.0 || Math.round(arr0[0] * arr0[1]) == 24.0) {
                        flag = true;
                        return;
                    }
                    if (arr0[0] != 0.0) {
                        if (Math.round(arr0[1] / arr0[0]) == 24.0) {
                            flag = true;
                            return;
                        }
                    }
                    if (arr0[1] != 0.0) {
                        if (Math.round(arr0[0] / arr0[1]) == 24.0) {
                            flag = true;
                            return;
                        }
                    }
                }

                return;
            }
                for (int i = start; i < arr.length; i++) {
                    if (list.contains(i)) {
                        continue;
                    }
                    list.add(i);
                    back3(list, arr, i + 1);
                    list.removeLast();
                }
            }


        }
    }


//leetcode submit region end(Prohibit modification and deletion)

